package net.tp.struct.bst;

import net.tp.struct.tree.AbstractBinNode;

/**
 *
 * @author Trung Phan
 */
public class DynamicOrderStatistics {

    /**
     * Find the ith smallest element in the bst sub-tree rooted at node.
     * @param node Tree root
     * @param i ith position
     * @param <N> Node type
     * @return the ith node.
     * @time $O(log n)$
     */
    public static <N extends AbstractBinNode<N>> N select(N node, int i) {

        if (node == null) return null;

        // calculate the rank k of the current node
        int k = (node.left != null ? node.left.size : 0);

        if (k == i) return node;
        else if (k < i) return select(node.right, i - k - 1);
        else return select(node.left, i);

    }


    public static <N extends AbstractBinNode<N>> int rank(N node) {
        return 0;
    }

}
